`
https://leetcode.cn/problems/word-search/
`

/**
 * @param {character[][]} board
 * @param {string} word
 * @return {boolean}
 */
var exist = function (board, word) {
  let isFound = false
  const m = board.length, n = board[0].length
  const used = Array.from({ length: m }, () => new Array(n).fill(false))

  function dfs(i, j, p) {
    // 已经找到，不需要遍历了
    if (isFound) return

    // 单词遍历完了，说明找到了
    if (p === word.length) {
      isFound = true
      return
    }

    // 边界
    if (i < 0 || j < 0 || i >= m || j >= n) return

    // 已经用过了
    if (used[i][j]) return

    // 判断是否是当前需要匹配的字母
    if (board[i][j] !== word[p]) {
      return
    }

    used[i][j] = true
    dfs(i + 1, j, p + 1)
    dfs(i - 1, j, p + 1)
    dfs(i, j + 1, p + 1)
    dfs(i, j - 1, p + 1)
    used[i][j] = false
  }

  // 遍历每一个点作为起点
  for (let i = 0; i < m; i++) {
    for (let j = 0; j < n; j++) {
      dfs(i, j, 0)
      if (isFound) return true
    }
  }

  return false
};